#include <iostream>
#include "triMulty.h"


node::node()
{
    minMulTimes = 0;
    for(int t = 0; t < 4; t ++)
        multiWay[t] = -1;
}

triMulty::triMulty()
{
    timeChart = NULL;
    trixs = NULL;
    trixsNum = 0;
}

int triMulty::getMinMultiTimes(int* t, int tn)
{
    trixsNum = tn;
    if(trixs != NULL)
        delete trixs;

    trixs = new int[trixsNum+1];              //注意这里要多一个位置
    for(int t1 = 0; t1 <= trixsNum; t1 ++)
    {
        trixs[t1] = t[t1];
    }
    //trixs[tn] =

    if(timeChart != NULL)
        delete timeChart;
    timeChart = new node[tn*tn];

    int i, j, k, tmp, init;
    for(int t1 = 1; t1 < trixsNum; t1 ++)
    {
        for(int t2 = 1; t2 <= trixsNum - t1; t2 ++)
        {
            i = t2;
            j = t2 + t1;
            init = 1;

            for(int t3 = i; t3 <= j-1; t3 ++)
            {
                k = t3;
                tmp =   (timeChart+((i-1)*trixsNum+(k-1)))->minMulTimes +
                        (timeChart+((k+1-1)*trixsNum+(j-1)))->minMulTimes +
                        trixs[i-1] * trixs[k+1-1] * trixs[j+1-1];


                if(init == 1)
                {
                    (timeChart+((i-1)*trixsNum+(j-1)))->minMulTimes = tmp;
                    (timeChart+((i-1)*trixsNum+(j-1)))->multiWay[0] = i;
                    (timeChart+((i-1)*trixsNum+(j-1)))->multiWay[1] = k;
                    (timeChart+((i-1)*trixsNum+(j-1)))->multiWay[2] = k+1;
                    (timeChart+((i-1)*trixsNum+(j-1)))->multiWay[3] = j;
                    init = 0;
                }

                if((timeChart+((i-1)*trixsNum+(j-1)))->minMulTimes > tmp)
                {
                    (timeChart+((i-1)*trixsNum+(j-1)))->minMulTimes = tmp;
                    (timeChart+((i-1)*trixsNum+(j-1)))->multiWay[0] = i;
                    (timeChart+((i-1)*trixsNum+(j-1)))->multiWay[1] = k;
                    (timeChart+((i-1)*trixsNum+(j-1)))->multiWay[2] = k+1;
                    (timeChart+((i-1)*trixsNum+(j-1)))->multiWay[3] = j;
                }
            }//for
            //std::cout << (timeChart+((i-1)*trixsNum+(j-1)))->minMulTimes << " ";
        }//for
        //std::cout << std::endl;
    }//for

    return (timeChart+((1-1)*trixsNum+(trixsNum-1)))->minMulTimes;
}


int triMulty::printWay(int b, int e)
{
    //node *tmpNode = (timeChart+((b-1)*trixsNum+(e-1)));
    if(b == -1)
    {
        node *tmpNode2 = (timeChart+((1-1)*trixsNum+(trixsNum-1)));
        //std::cout << "(";
        if(tmpNode2->multiWay[0] == tmpNode2->multiWay[1])
        {
            std::cout << "A" << tmpNode2->multiWay[0];
        }
        else
        {
            std::cout << "(";
            printWay((timeChart+((1-1)*trixsNum+(trixsNum-1)))->multiWay[0],
                    (timeChart+((1-1)*trixsNum+(trixsNum-1)))->multiWay[1]);

            std::cout << ")";
        }
         //std::cout << ")(";
        if(tmpNode2->multiWay[2] == tmpNode2->multiWay[3])
        {
            std::cout << "A" << tmpNode2->multiWay[2];
        }
        else
        {
            std::cout << "(";
            printWay((timeChart+((1-1)*trixsNum+(trixsNum-1)))->multiWay[2],
                    (timeChart+((1-1)*trixsNum+(trixsNum-1)))->multiWay[3]);
            std::cout << ")";
        }
        //std::cout << ")";
        std::cout << std::endl;
        return 1;
    }

    node *tmpNode = (timeChart+((b-1)*trixsNum+(e-1)));

    if(tmpNode->multiWay[0] == tmpNode->multiWay[1])
    {
        std::cout << "A" << tmpNode->multiWay[0];
    }
    else
    {
        std::cout << "(";
        printWay(tmpNode->multiWay[0], tmpNode->multiWay[1]);
        //std::cout << ")(";
        //printWay(tmpNode->multiWay[1]);
        std::cout << ")";
    }


    if(tmpNode->multiWay[2] == tmpNode->multiWay[3])
    {
        std::cout << "A" << tmpNode->multiWay[2];
    }
    else
    {
        std::cout << "(";
        printWay(tmpNode->multiWay[2], tmpNode->multiWay[3]);
        //std::cout << ")(";
        //printWay(tmpNode->multiWay[3]);
        std::cout << ")";
    }

    return 1;
}
